package bfs;


public class 图形渲染 {
	public static int l,r;
    public static int MAXM=51;
    public static int MAXN=51;
    //实际上，本题并不需要visit数组，但为了同一规范，还是写了
    public static boolean[][] visit;
    //枚举四个方向
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public static int[][] queue=new int[MAXM*MAXN][2];
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prev=image[sr][sc];
        if(prev==color){
            return image;
        }
        l=r=0;
        int m=image.length;
        int n=image[0].length;
        visit=new boolean[MAXM][MAXN];
        //本题第一层只有1个元素image[sr][sc]，直接入队列
        queue[r][0]=sr;
        queue[r++][1]=sc;
        visit[sr][sc]=true;
        //bfs
        while(l<r){
            int size=r-l;
            //处理一层节点
            for(int i=0;i<size;i++){
                int nx=queue[l][0];
                int ny=queue[l++][1];
                image[nx][ny]=color;
                //处理每个节点的相邻节点
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]==false&&image[x][y]==prev){
                        queue[r][0]=x;
                        queue[r++][1]=y;
                        visit[x][y]=true;
                    }
                }
            }
        }
        return image;
    }

}
